#反转字符串中的单词
class Solution:
    def reverseWords(self, s: str) -> str:
        s =s.strip()
        i = j = len(s)-1
        res = []
        while i >= 0:
            while i >= 0 and s[i] != ' ':i -=1
            res.append(s[i+1:j+1])
            while i >= 0 and s[i] == ' ':i -=1
            j = i
        return ' '.join(res)


#Z字形变换
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2: return s
        res = ["" for _ in range(numRows)]
        i, flag = 0, -1
        for c in s:
            res[i] += c
            if i == 0 or i == numRows-1: flag = -flag
            i += flag
        return ''.join(res)


#两数之和2
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i, j = 0, len(numbers)-1
        while i < j:
            s = numbers[i] + numbers[j]
            if s > target: j -=1
            elif s < target: i +=1
            else:return i+1, j+1
        return []


#乘最多水的容器
class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j = 0, len(height)-1
        maxa = 0
        while i != j:
            if height[i] < height[j]:
                maxa = max(maxa, height[i]*(j-i))
                temp = height[i]
                i += 1
                while height[i]<=temp:
                    i += 1
            else:
                maxa = max(maxa, height[j]*(j-i))
                temp = height[j]
                while height[j]<=temp and j!= i:
                    j -= 1
        return maxa


#三数之和
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res, k = [], 0
        for k in range(len(nums)-2):
            if nums[k]>0:break
            if k >0 and nums[k] == nums[k-1]:continue
            i, j = k+1, len(nums)-1
            while i < j:
                s = nums[k]+nums[i] +nums[j]
                if s < 0:
                    i += 1
                    while i < j and nums[i] == nums[i-1]:i += 1
                elif s > 0:
                    j -= 1
                    while i < j and nums[j] == nums[j+1]:j -= 1
                else:
                    res.append((nums[k], nums[i], nums[j]))
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i-1]: i+=1
                    while i < j and nums[j] == nums[j+1]: j-=1
        return res


#长度最小的子数组
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n+1
        s = left = 0
        for right, x in enumerate(nums):
            s += x
            while s - nums[left] >= target:
                s -= nums[left]
                left += 1
            if s >= target:
                ans = min(ans, right - left + 1)
        return ans if ans <= n else 0


#无重复字符的最长子串
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic, res, i = {}, 0, -1
        for j in range(len(s)):
            if s[j] in dic:
                i = max(dic[s[j]], i)
            dic[s[j]] = j
            res = max(res, j-i)
        return res


#有效的数独
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for i in range(9):
            storage = []
            for j in range(9):
                if board[i][j] == '.':
                    continue
                if board[i][j] in storage:
                    return False
                else:
                    storage.append(board[i][j])
        for i in range(9):
            storage = []
            for j in range(9):
                if board[j][i] == '.':
                    continue
                if board[j][i] in storage:
                    return False
                else:
                    storage.append(board[j][i])
        for i in range(0, 9, 3):
            for j in range(0, 9, 3):
                storage = []
                for x in range(0, 3):
                    for y in range(0, 3):
                        if board[i+x][j+y] == '.':
                            continue
                        if board[i+x][j+y] in storage:
                            return False
                        else:
                            storage.append(board[i+x][j+y])
        return True


#螺旋矩阵
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix: return []
        l, r, t, b, res = 0, len(matrix[0])-1, 0, len(matrix)-1, []
        while True:
            for i in range(l, r+1): res.append(matrix[t][i])
            t += 1
            if t > b:break
            for i in range(t, b+1): res.append(matrix[i][r])
            r -= 1
            if l > r:break
            for i in range(r, l-1, -1): res.append(matrix[b][i])
            b -= 1
            if t > b: break
            for i in range(b, t-1, -1): res.append(matrix[i][l])
            l += 1
            if l > r:
                break
        return res


#旋转图像
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range(n//2):
            for j in range((n+1)//2):
                tmp = matrix[i][j]
                matrix[i][j] = matrix[n-1-j][i]
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j]
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i]
                matrix[j][n-1-i] = tmp